package jiaoheng.数据结构;

import org.junit.Test;

import java.util.Deque;
import java.util.LinkedList;

public class s3栈 {
    // 最小栈，这时可以使用java自带的集合了
    @Test
    public void testMinStack(){
        // 测试方案一
        System.out.println("测试方案一：辅助栈法");
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println("当前最小值: " + minStack.getMin()); // 返回 -3
        minStack.pop();
        System.out.println("栈顶元素: " + minStack.top());    // 返回 0
        System.out.println("当前最小值: " + minStack.getMin()); // 返回 -2
    }
}
class MinStack{
    private Deque<Integer> mainStack;
    private Deque<Integer> minStack;

    public MinStack(){
        mainStack = new LinkedList<Integer>();
        minStack = new LinkedList<Integer>();
    }

    public void push(int x) {
        mainStack.push(x);
        if(minStack.isEmpty() || minStack.peek()>=x){ //这里需要大于等于 相等的需要都入库
            minStack.push(x);
        }
    }

    public void pop() {
        Integer popVal = mainStack.pop();
        if(minStack.peek().equals(popVal)){
            minStack.pop();
        }
    }

    public int top(){
        return mainStack.peek();
    }


    public int getMin() {
        return minStack.peek();
    }
}

